class Solution {
public:
    int respace(vector<string>& d, string s) 
    {
        //dp[i]代表从0到i位置的字符时一共存在多少个无法被识别的字符
        //然后就是动态转移方程了
        //如果dp[i]可以和前面的len个字符组成一个字符串，并且这个字符串在字典中是存在的，那么
        //dp[i] = dp[i-len];但是如果i位置的字符无论多长都无法和前面的字符组合成为一个字符串
        //那么此时的dp[i] = dp[i-1]+1
        //然后就是填写顺序了，因为在填写一个状态的时候我，我需要使用到前面的字符，所以需要从后往前遍历
        //最后返程dp[len]
        int len = s.size();
        int dp[len+1];
        dp[0] = 0;
        for(int i = 1;i<=len;i++)
        {
            dp[i] = dp[i-1]+1;
            for(int j = 0;j<d.size();j++)
            {
                int size = d[j].size();
                if(size <= i)
                {
                    if(s.substr(i-size,size)==d[j])
                        dp[i]=min(dp[i],dp[i-size]);
                }
            }
        }
        return dp[len];
    }
};